package leetcode.Hot100;

import leetcode.TreeNode;

import java.util.Arrays;

/**
 * @author Cheng Jun
 * Description: 从前序与中序遍历序列构造二叉树
 * 注意：前序与中序 遍历， 后序与中序 遍历都能 构造出二叉树，但是前序和后续 不能构造唯一的二叉树。
 *
 * 1 <= preorder.length <= 3000
 * inorder.length == preorder.length
 * -3000 <= preorder[i], inorder[i] <= 3000
 * preorder和 inorder均无重复元素
 * inorder均出现在preorder
 * preorder保证为二叉树的前序遍历序列
 * inorder保证为二叉树的中序遍历序列
 *
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 * @version 1.0
 * @date 2021/12/5 20:59
 */
public class buildTree {
    private int pre = 0;
    private int in = 0;

    public static void main(String[] args) {
        buildTree buildTree = new buildTree();
        System.out.println(buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7}));
        System.out.println(buildTree.buildTree1(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7}));
    }

    // 注意：条件中 preorder和 inorder均无重复元素，这是保证下面解法的关键
    // 根据 preorder 确定父节点，根据inorder 确定左右子节点
    // 递归实现
    static TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] != preorder[0]) {
                continue;
            } else {
                // 递归设置左右节点
                // 复制左右子节点的前序遍历和中序遍历（这也是提交LeetCode，速度慢的原因）
                root.left = buildTree(Arrays.copyOfRange(preorder, 1, 1 + i),
                        Arrays.copyOfRange(inorder, 0, i + 1));
                root.right = buildTree(Arrays.copyOfRange(preorder, 1 + i, preorder.length),
                        Arrays.copyOfRange(inorder, i + 1, inorder.length));
            }
        }
        return root;
    }

    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        return buildTreexa(preorder, inorder, Integer.MAX_VALUE + 1);
    }

    public TreeNode buildTreexa(int[] preorder, int[] inorder, long stop) {
        // 数组为空时返回null pre++一直在变化，初始为0，其最终值应等于preorder.length - 1, 二者相等说明为空数组
        if (pre == preorder.length) {
            return null;
        }
        // 中序遍历数组in位置节点等于该子树根节点值，说明此时已遍历到底部，返回null值（最左下角的元素，此时执行in++操作，同时返回当前节点null值
        if (inorder[in] == stop) {
            in++;
            return null;
        }
        // val值相当于将树中的所有节点 按中左右顺序对其进行遍历(先序遍历)
        int val = preorder[pre++];
        TreeNode root = new TreeNode(val);
        // 每个节点都获取其对应的左右子树值（包括null)
        root.left = buildTreexa(preorder, inorder, val);
        // 最右边（右下角）右子树上界为Integer.MAX_VALUE+1，其余右子树则不断更新上界，对应该子树根节点所在子树的公共祖先根节点值
        root.right = buildTreexa(preorder, inorder, stop);
        return root;
    }
}
